﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace soudu.sudo
{
    class Sudo
    {
        /*变量：data[][]二维数组用于存储数独的数字 mark[]用于计算某行某列的格子里不确定度（可以选择的数字）*/
        /**
         * 步骤：
         * 1、初始化第一行，随机1-9九个数字，打乱这九个数字的顺序
         * 2、随机将第一行的数字赋值给二维数组
         * 3、根据九个数字进行求解--有解返回true，无解返回false并重新生成数独求解
         */
        private  int[,] data = new int[9,9];//数独数组
        private  int lef;//数组中0的个数

        public int[,] getData()
        {
            getSudo();//初始化数独
            if (!solveSudo())//进行求解
            {
                //如果当前数独无解，则重新初始
                getSudo();
                return  getData();
            }
            return data;
        }
        //构造函数：给数独数组赋初值
        public Sudo()
        {
            lef = 0;//初始化0的个数
            for (int i = 0; i < 9; i++)
            {
                for (int j = 0; j < 9; j++)
                {
                    data[i,j] = 0;
                }
            }
        }
        
        //使用挖洞法生成数独
        public void getSudo()
        {
            lef = 81 - 9;
            for (int i = 0; i < 9; i++)
            {
                data[0,i] = i + 1;//初始化九个数字
            }
            //交换第一行的九个数字
            for (int i = 0; i < 9; i++)
            {
                var seed = Guid.NewGuid().GetHashCode();//生成随机数种子
                Random random = new Random(seed);//产生随机数
                int ta = random.Next(0,9);//返回1-9的随机数
                int temp = data[0,i];
                data[0,i] = data[0,ta];
                data[0,ta] = temp;
            }
            //随机将九个数字放入二维数组中
            for (int i = 0; i < 9; i++)
            {
                //生成需要交换的随机行列
                int ta = new Random(Guid.NewGuid().GetHashCode()).Next(0,9);
                int tb = new Random(Guid.NewGuid().GetHashCode()).Next(0,9);
                int temp = data[0,i];
                data[0,i] = data[ta,tb];
                data[ta,tb] = temp;
            }
        }
        /**
         * 调用回溯法进行求解：
         * 找到可行解则返回true，没有找到返回false
         */
        public Boolean solveSudo()
        {
            if (dfs())
            {
                return true;
            }
            else
            {
                return false;
                //没有找到解
            }
        }
        /**
         * calcount:求解每一个数据的不确定度，即根据同列同行同九宫格数值进行判断
         */
         private int calcount(int row,int cul,int[] mark)
        {
            for (int i = 0; i < 10; i++)
                mark[i] = 0;//初始化0-9十个数字对应的标记
            for (int i = 0; i < 9; i++)
            {
                mark[data[row, i]] = 1;
                mark[data[i, cul]] = 1;//同行同列标记
            }
            int rows = (row / 3) * 3;//所在九宫格
            int culs = (cul / 3) * 3;
            for (int i = 0; i < 3; i++)
                for (int j = 0; j < 3; j++)
                    mark[data[rows + i, culs + j]] = 1;
            int count = 0;
            for(int i = 0; i <= 9; i++)
            {
                if (mark[i] == 0)
                    count++;
            }
            return count;
        }
        /**
         * 使用dfs进行求解
         */
         private Boolean dfs()
        {
            if (lef == 0) return true;//不存在0的数字
            int mincount = 10;//初始不确定度
            int mini = 0, minj = 0;
            int[] mark = new int[10];
            /*找到不确定度最小的格子*/
            for (int i = 0; i < 9; i++)
            {
                for (int j = 0; j < 9; j++)
                {
                    if (data[i, j] != 0)
                        continue;//当已经存在数字的时候，跳出循环
                    int count = calcount(i, j, mark);//计算不确定度
                    if (count == 0) return false;//当格子为0且不确定度为0 的时候，返回错误
                    if(count < mincount)
                    {
                        mincount = count;
                        mini = i;
                        minj = j;//记录最小不确定度位置
                    }
                }
            }
            /*优先处理不确定度小的格子*/
            calcount(mini, minj, mark);
            for (int i = 0; i <= 9; i++)
            {
                if (mark[i] == 0)
                {
                    data[mini, minj] = i;
                    lef--;
                    dfs();
                    if (lef == 0)
                    {
                        return true;
                    }
                    data[mini, minj] = 0;//无解先置零
                    lef++;
                }
            }
            return true;
        }
    }
}
